
元组是一个容器，提供了访问和修改其每个元素的能力(通过get)，以及创建新的元组(直接或使用makeTuple())，并将元组分解为头部和尾部(getHead()和getTail())。这些基本构建块足以构建一套元组算法，例如从元组中添加或删除元素，重新排序元组中的元素，或选择元组中元素的某些子集。

元组算法特别有趣，因为同时需要编译时和运行时计算。与第24章的类型列表算法相同，将算法应用到元组可能会得到完全不同类型的元组，这需要编译时计算。对Tuple<int, double, string>进行反转会产生Tuple<string, double, int>，就像同构容器的算法(例如，std::vector上的std::reverse())一样，元组算法实际上需要在运行时执行代码，所以需要注意生成代码的效率。

\subsubsubsection{25.3.1\hspace{0.2cm}元组作为类型列表}

若忽略Tuple模板的实际运行时组件，会发现其结构与第24章中开发的类型列表模板完全相同:可以接受任意数量的模板类型参数。通过一些局部特化，可以将Tuple变成一个功能齐全的类型列表:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tupletypelist.hpp}
\begin{lstlisting}[style=styleCXX]
// determine whether the tuple is empty:
template<>
struct IsEmpty<Tuple<>> {
	static constexpr bool value = true;
};

// extract front element:
template<typename Head, typename... Tail>
class FrontT<Tuple<Head, Tail...>> {
	public:
	using Type = Head;
};

// remove front element:
template<typename Head, typename... Tail>
class PopFrontT<Tuple<Head, Tail...>> {
	public:
	using Type = Tuple<Tail...>;
};

// add element to the front:
template<typename... Types, typename Element>
class PushFrontT<Tuple<Types...>, Element> {
	public:
	using Type = Tuple<Element, Types...>;
};

// add element to the back:
template<typename... Types, typename Element>
class PushBackT<Tuple<Types...>, Element> {
	public:
	using Type = Tuple<Types..., Element>;
};
\end{lstlisting}

第24章中开发的所有类型列表算法，在Tuple和类型列表中也能工作，可以轻松地处理元组的类型:

\begin{lstlisting}[style=styleCXX]
Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
using T2 = PopFront<PushBack<decltype(t1), bool>>;
T2 t2(get<1>(t1), get<2>(t1), true);
std::cout << t2;
\end{lstlisting}

输出为

\begin{tcblisting}{commandshell={}}
(3.14, Hello, World!, 1)
\end{tcblisting}

应用于元组类型的类型列表算法，可用来确定元组算法的结果类型。

\subsubsubsection{25.3.2\hspace{0.2cm}添加和删除元素}

对于元组的值，在开头或结尾添加元素的能力对于构建更高级的算法很重要。与类型列表一样，在元组前面插入比在后面插入容易，所以先从pushFront开始:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/pushfront.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Types, typename V>
PushFront<Tuple<Types...>, V>
pushFront(Tuple<Types...> const& tuple, V const& value)
{
	return PushFront<Tuple<Types...>, V>(value, tuple);
}
\end{lstlisting}

现有元组的前面添加一个新元素(称为值)要求以值为头，以现有元组作为尾。产生的元组类型是Tuple<V, Types...>。但我们选择使用类型列表算法PushFront来演示元组算法的编译时和运行时间的耦合关系:编译时PushFront计算需要构造的类型，以产生运行时的值。

在现有元组的末尾添加新元素更为复杂，因为需要对元组进行递归遍历，并在遍历过程中构建修改后的元组。pushBack()实现的结构遵循第24.2.3节中类型列表pushBack()的递归公式:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/pushback.hpp}
\begin{lstlisting}[style=styleCXX]
// basis case
template<typename V>
Tuple<V> pushBack(Tuple<> const&, V const& value)
{
	return Tuple<V>(value);
}

// recursive case
template<typename Head, typename... Tail, typename V>
Tuple<Head, Tail..., V>
pushBack(Tuple<Head, Tail...> const& tuple, V const& value)
{
	return Tuple<Head, Tail..., V>(tuple.getHead(),
	pushBack(tuple.getTail(), value));
}
\end{lstlisting}

基本情况，通过生成只包含该值的元组，将值追加到零长度的元组。在递归的情况下，需要用列表头部的当前元素(tuple. gethead())，并将新元素添加到列表尾部的结果(递归pushBack调用)，组成一个新的元组。虽然将构造的类型表示为Tuple<Head, Tail..., V>，这相当于在编译时使用PushBack<Tuple<Head, Tail...>, V>。

另外，popFront()很容易实现:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/popfront.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Types>
PopFront<Tuple<Types...>>
popFront(Tuple<Types...> const& tuple)
{
	return tuple.getTail();
}
\end{lstlisting}

现在可以对25.3.1节中的示例进行编程:

\begin{lstlisting}[style=styleCXX]
Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
auto t2 = popFront(pushBack(t1, true));
std::cout << std::boolalpha << t2 << ’\n’;
\end{lstlisting}

输出为

\begin{tcblisting}{commandshell={}}
(3.14, Hello, World!, true)
\end{tcblisting}

\subsubsubsection{25.3.3\hspace{0.2cm}反转}

元组元素可以用另一种递归元组算法进行反转，该算法的结构遵循第24.2.4节的类型列表反转:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/reverse.hpp}
\begin{lstlisting}[style=styleCXX]
// basis case
Tuple<> reverse(Tuple<> const& t)
{
	return t;
}

// recursive case
template<typename Head, typename... Tail>
Reverse<Tuple<Head, Tail...>> reverse(Tuple<Head, Tail...> const& t)
{
	return pushBack(reverse(t.getTail()), t.getHead());
}
\end{lstlisting}

基本情况很简单，而递归情况则反转列表的尾部，并将当前头部元素追加到反转的列表中。

\begin{lstlisting}[style=styleCXX]
reverse(makeTuple(1, 2.5, std::string("hello")))
\end{lstlisting}

将产生一个Tuple<string, double, int>，其值分别为string("hello")，2.5和1。

和类型列表一样，可以通过调用popFront()来提供popBack()来反转列表，使用第24.2.4节中的popBack:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/popback.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Types>
PopBack<Tuple<Types...>>
popBack(Tuple<Types...> const& tuple)
{
	return reverse(popFront(reverse(tuple)));
}
\end{lstlisting}

\subsubsubsection{25.3.4\hspace{0.2cm}索引列表}

上一节中，元组反转递归公式是正确，但在运行时效率很低。为了了解这个问题，我们引入了简单的类，其会计算复制自己的次数:

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}C++17前，不支持内联静态成员，必须在一个翻译单元中初始化类结构外的numCopies。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/copycounter.hpp}
\begin{lstlisting}[style=styleCXX]
template<int N>
struct CopyCounter
{
	inline static unsigned numCopies = 0;
	CopyCounter() {
	}
	CopyCounter(CopyCounter const&) {
		++numCopies;
	}
};
\end{lstlisting}

创建并反转一个CopyCounter实例元组:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/copycountertest.hpp}
\begin{lstlisting}[style=styleCXX]
void copycountertest()
{
	Tuple<CopyCounter<0>, CopyCounter<1>, CopyCounter<2>,
			CopyCounter<3>, CopyCounter<4>> copies;
	auto reversed = reverse(copies);
	std::cout << "0: " << CopyCounter<0>::numCopies << " copies\n";
	std::cout << "1: " << CopyCounter<1>::numCopies << " copies\n";
	std::cout << "2: " << CopyCounter<2>::numCopies << " copies\n";
	std::cout << "3: " << CopyCounter<3>::numCopies << " copies\n";
	std::cout << "4: " << CopyCounter<4>::numCopies << " copies\n";
}
\end{lstlisting}

程序将输出:

\begin{tcblisting}{commandshell={}}
0: 5 copies
1: 8 copies
2: 9 copies
3: 8 copies
4: 5 copies
\end{tcblisting}

这么多次复制!元组反向的理想实现中，每个元素只会复制一次就够了，从源元组直接复制到结果元组中的正确位置。我们可以通过引用(包括使用中间参数类型的引用)来实现这一目标，但会使实现变得相当复杂。

为了在元组反向操作中消除多余的副本，考虑如何对已知长度的单个元组(如本例中为5个元素)实现一次性元组反向操作。可以简单地使用makeTuple()和get():

\begin{lstlisting}[style=styleCXX]
auto reversed = makeTuple(get<4>(copies), get<3>(copies),
							get<2>(copies), get<1>(copies),
							get<0>(copies));
\end{lstlisting}

这个程序产生了期望的输出，每个元组元素只有一个副本:

\begin{tcblisting}{commandshell={}}
0: 1 copies
1: 1 copies
2: 1 copies
3: 1 copies
4: 1 copies
\end{tcblisting}

索引列表(也称为索引序列;参见第24.4节)通过将元组索引集(本例中为4、3、2、1、0)捕获到参数包中来推广，并允许通过包展开产生get调用序列。计算索引(可以是复杂的模板元程序)与索引列表的应用程序可以分离开来。在索引列表中，运行时效率很重要。标准类型std::integer\_sequence(C++14中引入)用于表示索引列表。

\subsubsubsection{25.3.5\hspace{0.2cm}使用索引列表进行反转}

要使用索引列表对元组进行反转，首先需要索引列表，其是一个类型列表，包含的值可以用作类型列表或异构数据结构的索引(参见第24.4节)。对于索引列表，将使用24.3节中开发的Valuelist类型。与上面的元组反转示例对应的索引列表是

\begin{lstlisting}[style=styleCXX]
Valuelist<unsigned, 4, 3, 2, 1, 0>
\end{lstlisting}

要如何生成这个索引列表?一种方法是使用简单的模板元程序MakeIndexList生成一个从0到N - 1(包括)的索引列表，其中N是一个元组的长度:

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}C++14提供了一个类似的模板make\_index\_sequence，生成了std::size\_t类型的索引列表，以及更通用的make\_integer\_sequence，其允许选择特定的类型。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/makeindexlist.hpp}
\begin{lstlisting}[style=styleCXX]
// recursive case
template<unsigned N, typename Result = Valuelist<unsigned>>
struct MakeIndexListT
: MakeIndexListT<N-1, PushFront<Result, CTValue<unsigned, N-1>>>
{
};

// basis case
template<typename Result>
struct MakeIndexListT<0, Result>
{
	using Type = Result;
};

template<unsigned N>
using MakeIndexList = typename MakeIndexListT<N>::Type;
\end{lstlisting}

可以将此操作与类型列表Reverse组合，以生成相应的索引列表:

\begin{lstlisting}[style=styleCXX]
using MyIndexList = Reverse<MakeIndexList<5>>;
					// equivalent to Valuelist<unsigned, 4, 3, 2, 1, 0>
\end{lstlisting}

要执行反转，需要将索引列表中的索引捕获到非类型参数包中。这通过将索引集元组的reverse()算法实现分成两部分来处理的:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/indexlistreverse.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Elements, unsigned... Indices>
auto reverseImpl(Tuple<Elements...> const& t,
Valuelist<unsigned, Indices...>)
{
	return makeTuple(get<Indices>(t)...);
}

template<typename... Elements>
auto reverse(Tuple<Elements...> const& t)
{
	return reverseImpl(t,
	Reverse<MakeIndexList<sizeof...(Elements)>>());
}
\end{lstlisting}

在C++11中，返回类型必须声明为

\begin{lstlisting}[style=styleCXX]
-> decltype(makeTuple(get<Indices>(t)...))
\end{lstlisting}

和

\begin{lstlisting}[style=styleCXX]
-> decltype(reverseImpl(t, Reverse<MakeIndexList<sizeof...(Elements)>>()))
\end{lstlisting}

reverseImpl()函数模板将Valuelist参数中的索引捕获到参数包indices中，然后返回调用makeTuple()的结果，其参数通过使用捕获的索引集(对元组调用get()获得)。

reverse()算法本身仅形成相应的索引集，并将其提供给reverseImpl算法。索引作为模板元程序进行操作，不会产生运行时代码。唯一的运行时代码会在reverseImpl中生成，使用makeTuple()构造产生元组，因此元组元素只复制一次。

\subsubsubsection{25.3.6\hspace{0.2cm}打乱和选择}

上一节中用于形成反向元组的reverseImpl()函数模板，实际上不包含与reverse()操作相关的代码。相反，它只是从现有元组中选择一组特定的索引，并使用它们来组成一个新的元组。Reverse()提供了一组反向索引，但许多算法可以建立在这个核心元组的select()算法基础上:

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}C++11中，返回类型必须声明为\texttt{->}decltype(makeTuple(get<indices>(t)…))。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/select.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Elements, unsigned... Indices>
auto select(Tuple<Elements...> const& t,
			Valuelist<unsigned, Indices...>)
{
	return makeTuple(get<Indices>(t)...);
}
\end{lstlisting}

元组splat操作是建立在select()上的一个简单算法，其接受元组中的单个元素，将其复制并创建另一个元组，该元组具有该元素的一定数量的副本:

\begin{lstlisting}[style=styleCXX]
Tuple<int, double, std::string> t1(42, 7.7, "hello"};
auto a = splat<1, 4>(t);
std::cout << a << ’\n’;
\end{lstlisting}

会生成一个Tuple<double, double, double, double>，其中每个值都是get<1>(t)的副本，所以会输出

\begin{lstlisting}[style=styleCXX]
(7.7, 7.7, 7.7, 7.7)
\end{lstlisting}

给定元程序来生成“复制”索引集，该索引集由值I的N个副本组成，splat()是select()的直接应用:

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}C++11中，splat()的返回类型必须声明为\texttt{->}decltype(return-expression)。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/splat.hpp}
\begin{lstlisting}[style=styleCXX]
template<unsigned I, unsigned N, typename IndexList = Valuelist<unsigned>>
class ReplicatedIndexListT;

template<unsigned I, unsigned N, unsigned... Indices>
class ReplicatedIndexListT<I, N, Valuelist<unsigned, Indices...>>
: public ReplicatedIndexListT<I, N-1,
								Valuelist<unsigned, Indices..., I>> {
};

template<unsigned I, unsigned... Indices>
class ReplicatedIndexListT<I, 0, Valuelist<unsigned, Indices...>> {
	public:
	using Type = Valuelist<unsigned, Indices...>;
};

template<unsigned I, unsigned N>
using ReplicatedIndexList = typename ReplicatedIndexListT<I, N>::Type;

template<unsigned I, unsigned N, typename... Elements>
auto splat(Tuple<Elements...> const& t)
{
	return select(t, ReplicatedIndexList<I, N>());
}
\end{lstlisting}

即使是复杂的元组算法，也可以通过索引列表上的模板元程序和select()来实现，可以使用第24.2.7节中开发的插入排序，根据元素类型大小对元组进行排序。给定这样一个sort()函数，其能接受一个比较元组元素类型的模板元函数进行比较操作，这里可以按类型大小对元组元素进行排序:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{typelist/tuplesorttest.hpp}
\begin{lstlisting}[style=styleCXX]
#include <complex>

template<typename T, typename U>
class SmallerThanT
{
	public:
	static constexpr bool value = sizeof(T) < sizeof(U);
};

void testTupleSort()
{
	auto t1 = makeTuple(17LL, std::complex<double>(42,77), ’c’, 42, 7.7);
	std::cout << t1 << ’\n’;
	auto t2 = sort<SmallerThanT>(t1); // t2 is Tuple<int, long, std::string>
	std::cout << "sorted by size: " << t2 << ’\n’;
}
\end{lstlisting}

输出可能如下所示:

\begin{lstlisting}[style=styleCXX]
(17, (42,77), c, 42, 7.7)
sorted by size: (c, 42, 7.7, 17, (42,77))
\end{lstlisting}

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}结果的顺序取决于特定于平台。例如，double的大小可能比long long的大小更小、相同或更大
\end{tcolorbox}

sort()实现包括使用InsertionSort和元组select():

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}C++11中，sort()的返回类型必须声明为\texttt{->}decltype(return-expression)。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tuplesort.hpp}
\begin{lstlisting}[style=styleCXX]
// metafunction wrapper that compares the elements in a tuple:
template<typename List, template<typename T, typename U> class F>
class MetafunOfNthElementT {
	public:
	template<typename T, typename U> class Apply;
	template<unsigned N, unsigned M>
	class Apply<CTValue<unsigned, M>, CTValue<unsigned, N>>
	: public F<NthElement<List, M>, NthElement<List, N>> { };
};

// sort a tuple based on comparing the element types:
template<template<typename T, typename U> class Compare,
typename... Elements>
auto sort(Tuple<Elements...> const& t)
{
	return select(t,
					InsertionSort<MakeIndexList<sizeof...(Elements)>,
									MetafunOfNthElementT<
												Tuple<Elements...>,
												Compare>::template Apply>());
}
\end{lstlisting}

仔细查看InsertionSort的使用:要排序的实际类型列表是类型列表中的索引列表，并使用MakeIndexList<>构造，插入排序的结果是元组中的一组索引，然后将其提供给select()。但因为InsertionSort对索引进行操作，所以比较操作是比较两个索引。当考虑std::vector的某种索引时，这个更容易理解，如下(非元编程)示例:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/indexsort.hpp}
\begin{lstlisting}[style=styleCXX]
#include <vector>
#include <algorithm>
#include <string>

int main()
{
	std::vector<std::string> strings = {"banana", "apple", "cherry"};
	std::vector<unsigned> indices = { 0, 1, 2 };
	std::sort(indices.begin(), indices.end(),
			[&strings](unsigned i, unsigned j) {
				return strings[i] < strings[j];
			});
}
\end{lstlisting}

索引包含vector字符串的索引,sort()操作对实际的索引进行排序，因此作为比较操作提供的Lambda接受两个无符号值(而不是字符串值)。但Lambda函数体可以使用无符号值作为字符串vector的索引，因此排序实际上是根据字符串内容进行的。排序的最后，索引提供字符串的索引，并根据字符串中的值排序。

我们对元组sort()的InsertionSort使用了相同的方法。适配器模板MetafunOfNthElementT提供了模板元函数(其嵌套的Apply)，该函数接受两个索引(CTValue特化)，并使用NthElement从类型列表参数中提取相应的元素。成员模板Apply“捕获”了提供给外围模板(MetafunOfNthElementT)的类型列表，与Lambda从其外围作用域捕获字符串vector的方式相同。然后，Apply将提取的元素类型转发给底层元函数F，完成调整。

排序的所有计算都在编译时执行，直接形成结果元组，在运行时没有多余的值复制。

















